{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 三数之和【困难】"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个数组和目标数target，找出数组中a,b,c满足a+b+c = target的所有组合。\n",
    "\n",
    "例如:\n",
    "\n",
    "arr = [-3,-1,-2,1,2,3],target = 0\n",
    "\n",
    "输出为[(-3,1,2),(-2,-1,3)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================答题区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================答题区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================提示区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#  提示：可以用字典进行查找减少一次搜索\n",
    "#  或者排序后从首尾同时搜索，这种方法比较巧妙\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================提示区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(-3, 1, 3), (-2, 1, 2), (-1, -3, 5)}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#==============================答案区==============================#\n",
    "# 解题思路1：使用字典\n",
    "# 遍历arr,使用字典存储两个元素的和以及它们的下标\n",
    "# 这种方法的时间复杂度O(n**2)，空间复杂度O(n**2)\n",
    "\n",
    "arr = [-1,-2,-3,1,2,3,5]\n",
    "\n",
    "def f(arr,target):\n",
    "    dic = {}\n",
    "    ans = set()\n",
    "    for k,c in enumerate(arr):\n",
    "        pairs = dic.get(target-c,None)\n",
    "        if pairs:\n",
    "            ans.update({(arr[i],arr[j],c) for i,j in pairs})\n",
    "        for i,a in enumerate(arr[0:k]):\n",
    "            dic[a+c] = dic.get(a+c,[])+[(i,k)]\n",
    "    return(ans)\n",
    "        \n",
    "f(arr,1)                 \n",
    "#==============================答案区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(-3, -1, 5), (-2, 1, 2), (-1, 1, 1)}"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#==============================答案区==============================#\n",
    "# 解题思路2：排序后首尾同时扫描查找\n",
    "# 这种方法的时间复杂度为O(n**2),且空间复杂度为O(1)\n",
    "\n",
    "def f(arr,target):\n",
    "    assert len(arr)>=3\n",
    "    arr.sort()\n",
    "    ans = set()\n",
    "    for k,c in enumerate(arr):\n",
    "        i,j = k+1,len(arr)-1\n",
    "        while i<=j:\n",
    "            if arr[i]+arr[j]+c <target:\n",
    "                i = i+1\n",
    "            elif arr[i]+arr[j]+c > target:\n",
    "                j = j-1\n",
    "            else:\n",
    "                ans.update({(arr[k],arr[i],arr[j])})\n",
    "                break\n",
    "    return(ans)\n",
    "\n",
    "f([-1,-2,-3,1,2,3,5],1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](../Python与算法之美.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
